Naivna gramatika
-------------------------------
E -> E + T
    | E - T
    | T
T -> T * F
    | T / F
    | F
    ;
F -> ( E )
    | - F
    | BROJ_T
    ;

LL(1) gramatika     Skupovi izbora              Akcije
----------------------------------------------------------------------
E -> T EP           (, -, BROJ_T                EP.inh = T.sin; E.sin = Ep.sin;
    ;
EP1 -> + T EP2      +                           EP2.inh = EP1.inh + T.sin; EP1.sin = EP2.sin;
    | - T EP2       -                           EP2.inh = EP1.inh - T.sin; EP1.sin = EP2.sin;
    | eps           ), EOI                      EP1.sin = EP2.sin;
T -> F TP           (, -, BROJ_T                TP.inh = F.sin; T.sin = TP.sin;
    ;
TP1 -> * F TP2      *                           TP2.inh = TP1.inh * F.sin; TP1.sin = TP2.sin;
    | / F TP2       /                           TP2.inh = TP1.inh / F.sin; TP1.sin = TP2.sin;
    | eps           ), EOI, +, -                TP1.sin = TP2.sin;
    ;
F1 -> ( E )         (                           F1.sin = E.sin;
    | - F2          -                           F1.sin = -F2.sin;
    | BROJ_T        BROJ_T                      F1.sin = - BROJ_TE.val;
    ;

Simbol  | First         | Eps   | Follow
---------------------------------------------------------------------
E       | (, -, BROJ_T  | /     | EOI, )
---------------------------------------------------------------------
EP      | +, -          | DA    | EOI, )
---------------------------------------------------------------------
T       | (, -, BROJ_T  | /     | EOI, ), +, -
---------------------------------------------------------------------
TP      | *, /          | DA    | EOI, ), +, -
---------------------------------------------------------------------
F       | (, -, BROJ_T  | /     | EOI, ), +, -, *, /
---------------------------------------------------------------------

Izvršavanje programa
----------------------------------------------------------------------

Da bismo odredili vrednost izraza potrebno je da svakom pravilu u gramatici dodelimo odgovarajuće akcije. 
Gramatika koju smo napisali je LL(1), tj. parsiranje radimo odozgo na dole. Parsiranje odozgo na dole znači da 
krećemo od startnog simbola gramatike i sukcesivnom zamenom neterminala njihovom desnom stranom želimo da dobijemo 
niz tokena na ulazu. Tokom parsiranja implicitno kreiramo stablo izvođenja, dok izračunavanju izraza, tj. izvršavanju
programa odgovara obilazak tog stabla. Da bismo uopšte išta mogli da izračunamo potrebno je da pored tokena saznamo i 
vrednosti koje su tokenima pridružene. Preciznije, nije dovoljno da znamo da se radi o tokenu BROJ_T, već lekser mora
da nam saopšti i koja je vrednost tog broja.

Problem na koji odmah nailazimo se krije u činjenici da vrednost tokena možemo da saznamo tek kada token izvedemo. U praksi, 
to znači da vrednosti koje su nam potrebne za izračunavanje saznajemo u listovima stabla. Da bismo išta izračunali, vrednosti
tokena moramo da propagiramo na gore uz stablo sve do neterminala koji opisuju deo izraza koji trenutno računamo. Vrednosti 
koje na taj način propagiramo uz stablo zvaćemo sintetisanim vrednostima. Zahvaljujući ovakvom pristupu, konačni rezultat ćemo 
dobiti tek kada se vratimo nazad do korena stabla, tj. startnog simbola.

Izračunavanju u LL(1) gramatici odgovara izvođenje na levo, što znači da vrednosti, tj. međurezultate uvek sintetišemo prvo
u levom podstablu. Da bismo izračunavanje dovršili, međurezultat iz levog podstabla moramo da prebacimo u desno podstablo i 
da ga propagiramo niz desno podstablo sve dok ne dođemo do tačke gde je izračunavanje moguće. Prebacivanje sintetisanih atributa
iz levog podstabla u desno se naziva nasleđivanje vrednosti.

Imajući u vidu da naši podavi teku niz stablo (nasleđivanje) i uz stablo (sintetisanje) svakom neterminalu ćemo da pridružimo dva
atributa `inh` i `sin`. `inh` atribut će čuvati nasleđene vrednosti neophodne za dalje izračunavanje, dok će `sin` atribut čuvati
konačne, tj. sintetisane rezultate izračunate u datom neterminalu. Iako mogu imati oba atributa, često se dešava da nekim
neterminalima nije potreban `inh` atribut.

Da bismo lakše razumeli o čemu se radi dovoljno je da pogledamo pravilo:

E -> T EP
    ;

i primer izraza 3 + 5. Ako pažljivije pogledamo pravilo i primer, jasno je da će u izvođenju pravila E -> T EP, neterminal T 
predstavljati prvi sabirak (3), dok će neterminal EP predstavljati ostatak izraza. Odavde je lako zaključiti da ostatak
izraza ne možemo da izračunamo bez znanja vrednosti prvog sabirka. Dakle, neterminal EP mora da nasledi vrednost prvog sabirka 
od neterminala T. Takođe, vrlo lako se zaključuje da konačnu vrednost neterminala E možemo da saznamo tek onda kada izračunamo
konačnu vrednost neterminala EP. Zbog toga, niz akcija koje treba da preduzmemo u pravili E je sledeće:

EP.inh = T.sin;         // da bismo uopšte mogli da izračunamo ostatak izraza, prvo treba da mu saopštimo kolika je vrednost prvog sabirka
E.sin = EP.sin;         // nakon što izračunamo ukupan zbir, to će biti ukupna vrednost izraza

Na sličan način možemo da objasnimo šta se dešava u pravilu

EP -> + T EP
    ;

S obzirom da se u pravilu i sa leve i sa desne strane javlja neterminal EP, numerisaćemo ih radi lakšeg objašnjenja akcija. Nakon 
numerisanja naše pravilo postaje;


EP1 -> + T EP2
    | eps
    ;



U grani EP1 -> + T EP2, jasno je da je vrednost prvog sabirka zapravo nasledjeni atribut pravila EP1. Nakon što saznamo vrednost 
drugog sabirka (T u zagradi), jasno je da će zbir te dve vrednosti biti nasleđeni atribut za eventualni ostatak zbira. 
Akcije pridružene pravilu če biti

EP2.inh = EP1.inh + T.sin
EP1.sin = EP2.sin

Sa druge strane, u grani EP1 -> eps, jasno je da smo izveli čitav izraz i da je ono što smo nasledili zapravo konačan rezultat. 
Akcija će u ovom slučaju biti:

EP1.sin = EP1.inh

Tokom parsiranja izraza 3 + 5 + 9, imaćemo sledeći niz izvođenja:

E -> T EP -> F EP -> BROJ_T(3) EP -> / vraćanje rekurzije, tj. sintetisanje / -> F.sin(3) EP
  -> T.sin(3) EP -> / izvođenje pravila EP1 -> + T EP2, EP1.inh = T.sin = 3 / -> 3 + T EP2
  -> 3 + F EP2 -> 3 + BROJ_T (5) EP2 -> / vraćanje rekurzije, tj. sintetisanje / -> 3 + F.sin(5) EP2
  -> 3 + T.sin(5) EP2 -> / kad znamo oba sabirka vrsimo akciju EP2.inh = EP1.inh + T.sin /
  -> 8 EP2 -> 8 + T EP3 -> 8 + F EP3 -> 8 + BROJ_T(9) EP3 -> / vraćanje rekurzije, tj. sintetisanje /
  -> 8 + F.sin(9) EP3 -> 8 + T.sin(9) EP3 -> / kad znamo oba sabirka vrsimo akciju EP3.inh = EP2.inh + T.sin /
  -> 17 EP3 -> / ulazu je EOF, pa vrsimo akciju EP3.sin = EP3.inh / -> EP3.sin(17) -> / sintetisanje //
  -> / EP2.sin = EP3.sin/ -> EP2.sin(17) -> /EP1.sin = EP2.sin/ -> EP1.sin(17) -> / E.sin = EP1.sin / -> E.sin = 17 

Dakle, izračunata vrednost izraza na kraju je 17.


Praktična implementacija
----------------------------------------------------------------------

Kao i do sada, implementaciju parsera možemo da izvršimo uz pomoć rekurzivnog spusta ili potisnog automata. 

Implementacija pomoću rekurzivnog spusta je izuzetno jednostavna. Nasleđeni atributi postaju argumenti funkcija
kojima su pravila predstavljena, dok sintetisani atributi, tj. rezultati izvršavanja postaju povratne vrednosti. 
Iz opisanog, očigledno je da omogućavanje izračunavanja izraza  u parseru implementiranom pomoću rekurzivnog spusta 
minimalno razlikuje od do sada napisanih programa. 

Kada se radi o potisnom automatu, izračunavanje se ne može direktno omogućiti minimalnim izmenama kao u slučaju 
rekurzinog spusta. Razlog za to je vrlo jednostavan. Rekurzivni spust koristi argumente funkcija i sistemski stek
da bi pamtio međurezultate, dok redosledom pozivanja funkcija upravlja akcijama i samim izračunavanjem. Potisni automat
u svojoj osnovnoj verziji na steku čuva samo tipove tokena i neterminale i u zavisnosti od toga šta je na vrhu steka i 
vrednosti preduvidnog simbola odlučuje šta skida i šta stavlja na stek.

Očigledno je da moramo da rešimo sledeće probleme:

1. Vrednosti tokena i međurezultate moramo da čuvamo tokom izvršavanja programa. Da bismo to omogućili, u program uvodimo
   novi stek na kojem čuvati vrednosti, tj. međurezultate. 
2. Potisni automat mora da zna kada treba da izvrši izračunavanje. Da bismo to omogućili uvodima stanja-akcije kojima ćemo
   naterati potisni automat da izračuna vrednosti onda kada treba. 
3. Ukoliko imamo više mogućih vrednosti tokena poput brojeva i stringova, za svaki tip bismo morali da imamo odvojeni stek. 
   Jasno je da ovakav pristup nije dobar jer vodi ka nepotrebnoj eksploziji složenosti koda. To se najčešće rešava implementacijom 
   hijerarhije tipova kojom se omogućava uniformno korišćenje svih tipova podataka u programu. 